package linkedList.迭代;

import linkedList.BaseLinkedListTest;
import po.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 链表组件817.java
 * @Description TODO
 * @createTime 2021年03月16日 19:12:00
 */
public class 链表组件817 extends BaseLinkedListTest {
    /**
     * 给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。
     * <p>
     * 同时给定列表 G，该列表是上述链表中整型值的一个子集。
     * <p>
     * 返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
     * <p>
     * todo 因为G是子集，G中的数不是有序的，所以不能对G进行排序的处理。又G中的数是不重复的，并且是链表中所有值得一个子集，如果要查询组件的个数，必须对链表进行遍历，并一一对比G中是否包含这个数。
     * todo 规则是G中的数可以不是连续的但是在链表中存在即可，
     * todo 举例G为 1 4 2 ，链表为 1 2 3 4 5 。那么存在两个组件，1 4 和 2。因为链表中 1 2 是连续的在G中也存在，4在链表中G中也存在，而5在链表中却不在G中所以不算，结果就是只有两个组件
     */
    public static int numComponents(ListNode head, int[] G) {
        //todo 把G转化为一个map或者set集合
        Set<Integer> gSet = new HashSet<>(G.length);
        for (int i : G) {
            gSet.add(i);
        }
        int size = 0;
        //todo 遍历链表
        while (head != null) {
            int length = 0;
            //todo 如果链表中的值在数组G中，则进行链表迭代，直到G中不存当前链表的值，然后结束当前的迭代，并把迭代的数据算作一个组件。最后进入下一轮
            while (head != null && gSet.contains(head.val)) {
                length++;
                head = head.next;
            }
            if (length!=0){
                size++;
            }
            //todo 如果不包含或者找到了一个组件，进入下一个节点继续找，因为G中不存在重复的
            if (head!=null){
                head=head.next;
            }
        }
        return size;
    }

    public static void main(String[] args) {
        numComponents(createLinkedList(0,1,2,3,4,5),new int[]{5,4,0, 3, 1});
    }
}
